﻿namespace Leetcode.N0587;

public class Solution
{
    public int[][] OuterTrees(int[][] trees)
    {
        if (trees.Length <= 3)
        {
            return trees;
        }
        int left = 0;
        for (int i = 1; i < trees.Length; i++)
        {
            if (trees[i][0] < trees[left][0])
            {
                left = i;
            }
        }
        var result = new List<int>();
        var visited = new bool[trees.Length];

        var current = left;
        do
        {
            int next = (current + 1) % trees.Length;

            for (int i = 0; i < trees.Length; i++)
            {
                if (this.Cross(trees[current], trees[next], trees[i]) < 0)
                {
                    next = i;
                }
            }

            for (int i = 0; i < trees.Length; i++)
            {
                if (visited[i] || i == current || i == next)
                {
                    continue;
                }
                if (Cross(trees[current], trees[next], trees[i]) == 0)
                {
                    result.Add(i);
                    visited[i] = true;
                }
            }

            if (visited[next] == false)
            {
                visited[next] = true;
                result.Add(next);
            }
            current = next;

        } while (current != left);

        return result.Select(_ => trees[_]).ToArray();
    }

    private int Cross(int[] p, int[] q, int[] r)
    {
        return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0]);
    }

}